#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode(){
    link = nullptr;
    dest = 0; 
}

EdgeNode::EdgeNode(int d, EdgeNode* l){
    link = l;
    dest = d;
}

EdgeNode::~EdgeNode() = default;

int EdgeNode::getDest(){
    return dest;
}

EdgeNode* EdgeNode::getNext(){
    return link;
}

void EdgeNode::setDest(int d){
    dest = d;
}

void EdgeNode::setNext(EdgeNode* l){
    link = l;
};

VertexNode::VertexNode(){
    data = '\0';
    firstEdge = nullptr;
}

VertexNode::VertexNode(char d, EdgeNode* fe){
    data = d;
    firstEdge = fe;
}

VertexNode::~VertexNode() = default;

char VertexNode::getData(){
    return data;
}

EdgeNode* VertexNode::getFirstEdge(){
    return firstEdge;
}

void VertexNode::setData(char d){
    data = d;
}

void VertexNode::setFirstEdge(EdgeNode* fe){
    firstEdge = fe;
};

MyGraph::MyGraph(){
    nodeNum = 0;
    edgeNum = 0;
    VexList = nullptr;
    visited = nullptr;
};

MyGraph::MyGraph(int nodeN, int edgeN, char* nodeL, int* edgeStartL, int* edgeEndL){
    nodeNum = nodeN;
    edgeNum = edgeN;
    int *count = new int[nodeN];
    visited = new int[nodeN];
    for(int i = 0; i < nodeN; i ++){
        count[i] = 0;
        visited[i] = 0;
    }
    VexList = new VertexNode[nodeN];
    for(int i = 0; i < nodeN; i ++){
        VexList[i].setData(nodeL[i]);
    }
    for(int i = 0; i < edgeN; i ++){
        int a = edgeStartL[i];
        int b = edgeEndL[i];
        count[a] ++;
        EdgeNode* aedge = new EdgeNode(b, nullptr); 
        aedge->setNext(VexList[a].getFirstEdge());
        VexList[a].setFirstEdge(aedge);
    }
    for(int i = 0; i < edgeN; i ++){
        int a = edgeStartL[i];
        int b = edgeEndL[i];
        EdgeNode* bedge = new EdgeNode(a, nullptr);
        if(count[b] == 0){
            bedge -> setNext(VexList[b].getFirstEdge());
            VexList[b].setFirstEdge(bedge);
            continue;
        }
        EdgeNode* p = VexList[b].getFirstEdge();
        if(count[b] > 1){
            for(int i = 1; i < count[b]; i ++)
                p = p -> getNext();
        }
        bedge -> setNext(p -> getNext());
        p -> setNext(bedge);
    }
    delete [] count;
}

MyGraph::~MyGraph() = default;

int MyGraph::getNodeNum(){
    return nodeNum;
}

int MyGraph::getEdgeNum(){
    return edgeNum;
}

string MyGraph::printGraph(){
    string s = "";
    for(int i = 0; i < nodeNum; i ++){
        s += VexList[i].getData();
        s += ": ";
        if(VexList[i].getFirstEdge() != nullptr){
            EdgeNode* p = VexList[i].getFirstEdge();
            s += VexList[p -> getDest()].getData();
            while(p -> getNext() != nullptr){
                p = p -> getNext();
                s += " ";
                s += VexList[p -> getDest()].getData();
            }
            if(i == nodeNum - 1)
                break;
            s += '\n';
        }
    }
    return s;
}

int MyGraph::getFirstNeighbor(int v, int* visited){
    int index = VexList[v].getFirstEdge() -> getDest();
    EdgeNode* p = VexList[v].getFirstEdge();
    while(visited[index] == 1 && p != nullptr){
            index = p -> getDest( );
            p = p -> getNext( );
    }
    if(p != nullptr){
        visited[index] = 1;
        return index;
    }
    return -1;
}

int MyGraph::getNextNeighbor(int v, int w, int* visited){
    EdgeNode* p = VexList[v].getFirstEdge();
    int index = -1;
    while(p != nullptr && index != w){
        index = p -> getDest( );
        p = p -> getNext( );
    }
    if(p != nullptr){
        while(visited[index] == 1 && p != nullptr){
            index = p -> getDest( );
            p = p -> getNext( );
        }
        if(visited[index])
            return -1;
        visited[index] = 1;
        return index;
    }
    return -1;
}

void MyGraph::DFS(int v, int* visited, string& result){
    visited[v] = 1;
    result += VexList[v].getData( );
    result += ' ';
    int indexa = getFirstNeighbor(v, visited);
    while(indexa != -1){
        DFS(indexa, visited, result);
        indexa = getNextNeighbor(v, indexa, visited);
    }
}

string MyGraph::graph_DFS_Traverse(){
    string dfs_order = "";
    for(int i = 0; i < nodeNum; i ++)
        visited[i] = 0;
    for(int i = 0; i < nodeNum; i ++){
        if(!visited[i]){
            DFS(i, visited, dfs_order); 
            }
    }
    return dfs_order;
}

graph_queue::graph_queue(){
    first = last = nullptr;
    num = 0;
};
graph_queue::~graph_queue() = default;
bool graph_queue::enqueue(int a){
    queueNode* q = new queueNode;
    q -> data = a;
    q -> next = nullptr;
    if(isempty()){
        first = q;
        last = q;
    }
    else{
        last -> next = q;
        last = q;
    }
    return 1;
};
bool graph_queue::popqueue(int& a){
    if(isempty())
        return 0;
    a = first -> data;
    queueNode* q = first;
    first = q -> next;
    delete q;
    return 1;
};
bool graph_queue::isempty(){
    return(first == nullptr);
};

void MyGraph::BFS(int v, int* visited, string& result){
    visited[v] = 1;
    graph_queue queue;
    queue.enqueue(v);
    while(!queue.isempty()){
        queue.popqueue(v);
        int indexa = getFirstNeighbor(v, visited);
        if(indexa != -1){
            result += VexList[indexa].getData( );
            result += ' ';            
            queue.enqueue(indexa);
        }
        indexa = getNextNeighbor(v, indexa, visited);
        while(indexa != -1){
            queue.enqueue(indexa);
            result += VexList[indexa].getData( );
            result += ' ';
            indexa = getNextNeighbor(v, indexa, visited);
        } 
    }
}

string MyGraph::graph_BFS_Traverse(){
    string bfs_order = "";
    int count = 0;
    for(int i = 0; i < nodeNum; i ++)
        visited[i] = 0;
    for(int i = 0; i < nodeNum; i ++){
        if(!visited[i]){
            bfs_order += VexList[i].getData( );
            bfs_order += ' ';
            BFS(i, visited, bfs_order); 
            }
    }
    return bfs_order;
}
